package com.cat.chapter045;

/**
 * @author cat
 * @description https://leetcode.cn/problems/ms70jA/
 * @create 2025/7/14 13:58
 * @since JDK17
 */

public class Solution01 {
    static int MAXN = ((int) (1e5 + 1));
    static int[][] tree = new int[MAXN][2];
    static int cnt = 1; // 只管有路就行了
    static int ans;

    void insert(String num) {   // 建路
        int cur = 1;
        for (int i = 0; i < num.length(); i++) {
            int path = num.charAt(i) - '0';
            if (tree[cur][path] == 0) { // 没路，就建
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
        }
    }

    void f(String num) {
        int cur = 1, x = 0;
        for (int i = 0; i < num.length(); i++) {
            int path = '1' - num.charAt(i);
            if (tree[cur][path] != 0) {     // 有则添一
                x |= 1 << i;
            }
        }
        ans = Math.max(ans, x);
    }

    public int findMaximumXOR(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            insert(Integer.toBinaryString(nums[i]));
        }
        for (int i = 0; i < nums.length; i++) {
            f(Integer.toBinaryString(nums[i]));
        }
        return ans;
    }
}
